package 单周赛.history;

import java.util.*;

/**
 *
 */
public class 第324场单周赛 {

    public static void main(String[] args) {

        System.out.println(similarPairs(new String[]{"nba", "cba", "dba"}));

        System.out.println(new 第324场单周赛().smallestValue(3));

        第324场单周赛 impl = new 第324场单周赛();
//        int[][] arr = new int[][]{{2, 7}, {6, 20}, {7, 19}, {12, 13}, {4, 9}, {11, 20}, {11, 13}, {3, 6}, {3, 7}, {3, 4}, {1, 8}, {18, 4}, {16, 6}, {6, 11}, {9, 16}, {15, 4}, {13, 3}, {14, 3}, {18, 12}, {8, 14}, {15, 2}, {7, 15}, {4, 11}, {13, 20}, {20, 18}, {20, 10}, {20, 3}, {15, 3}, {4, 8}, {10, 1}, {19, 15}};
//        int[][] arr = new int[][]{{1, 2}, {1, 3}, {1, 4}, {4, 5}, {5, 6}};
//        int[][] arr = new int[][]{{4, 1}, {3, 2}, {2, 1}, {3, 4}, {1, 5}, {2, 5}, {4, 6}, {3, 6}};
        int[][] arr = new int[][]{{2, 19}, {16, 17}, {8, 14}, {2, 16}, {12, 20}, {12, 14}, {16, 18}, {15, 16}, {10, 21}, {3, 5}, {13, 18}, {17, 20}, {14, 17}, {9, 12}, {5, 15}, {5, 6}, {3, 7}, {2, 21}, {10, 13}, {8, 16}, {7, 18}, {4, 6}, {9, 1}, {13, 21}, {18, 20}, {7, 14}, {4, 19}, {5, 8}, {3, 11}, {11, 1}, {7, 12}, {4, 7}, {3, 16}, {13, 17}, {17, 19}, {9, 13}, {7, 19}, {10, 16}, {4, 13}, {4, 5}, {2, 15}, {12, 19}, {11, 16}, {2, 9}, {11, 17}, {17, 1}, {16, 21}, {4, 10}, {10, 14}, {14, 16}, {4, 1}, {13, 20}, {5, 20}, {4, 14}, {4, 21}, {10, 20}, {2, 14}, {8, 15}, {4, 8}, {6, 19}, {15, 1}, {19, 1}, {8, 19}, {15, 21}, {3, 12}, {11, 18}, {9, 17}, {18, 19}, {7, 21}, {3, 21}, {16, 19}, {11, 15}, {5, 1}, {8, 17}, {3, 15}, {8, 1}, {10, 19}, {3, 8}, {6, 16}, {2, 8}, {5, 18}, {11, 13}, {11, 20}, {14, 21}, {6, 20}, {4, 20}, {12, 13}, {5, 12}, {10, 11}, {9, 15}, {3, 19}, {9, 20}, {14, 18}, {21, 1}, {13, 19}, {8, 21}, {2, 13}, {3, 10}, {9, 18}, {19, 21}, {6, 7}, {3, 18}, {2, 18}, {6, 14}, {3, 17}, {5, 21}, {14, 20}, {8, 9}, {16, 1}, {3, 4}, {13, 1}, {5, 9}, {4, 15}, {17, 21}, {20, 21}, {2, 17}, {13, 14}, {11, 14}, {9, 16}, {10, 18}, {6, 15}, {6, 12}, {3, 13}, {5, 11}, {6, 1}, {12, 17}, {8, 10}, {5, 10}, {8, 18}, {4, 12}, {10, 1}, {6, 13}, {4, 18}, {7, 20}, {7, 16}, {2, 6}, {12, 21}, {4, 17}, {15, 18}, {13, 16}, {15, 20}, {7, 10}, {6, 10}, {2, 20}, {7, 15}, {18, 1}, {12, 1}, {3, 20}, {7, 1}, {14, 15}, {4, 9}, {11, 19}, {7, 9}, {5, 17}, {18, 21}, {6, 21}, {8, 11}, {6, 17}, {3, 14}, {7, 11}, {5, 7}, {7, 13}, {6, 8}, {6, 9}, {10, 12}, {5, 16}, {2, 4}, {17, 18}, {9, 11}, {12, 16}, {3, 6}, {12, 18}, {3, 9}, {11, 12}, {14, 19}, {10, 15}, {5, 13}, {8, 13}, {15, 17}, {2, 10}, {11, 21}, {20, 1}, {6, 18}, {2, 12}, {19, 20}, {6, 11}, {8, 12}, {2, 3}, {12, 15}, {2, 11}, {9, 10}, {7, 17}, {9, 19}, {13, 15}, {7, 8}, {4, 11}, {2, 5}, {5, 19}, {16, 20}, {15, 19}, {9, 14}, {14, 1}, {10, 17}, {9, 21}, {2, 7}, {8, 20}, {5, 14}, {4, 16}};

        List<List<Integer>> edges = new ArrayList<>();
        for (int[] ints : arr) {
            List<Integer> list = new ArrayList<>();
            for (int anInt : ints) {
                list.add(anInt);
            }
            edges.add(list);
        }
        System.out.println(impl.isPossible(21, edges));

    }

    public static int similarPairs(String[] words) {
        int count = 0;

        for (int i = 0; i < words.length; i++) {
            int[] iArr = new int[26];
            for (char c : words[i].toCharArray()) {
                iArr[c - 'a']++;
            }

            for (int j = i + 1; j < words.length; j++) {
                int[] jArr = new int[26];
                for (char c : words[j].toCharArray()) {
                    jArr[c - 'a']++;
                }

                boolean flag = true;
                for (int r = 0; r < iArr.length; r++) {
                    if (iArr[r] > 0 && jArr[r] == 0 ||
                            jArr[r] > 0 && iArr[r] == 0) {
                        flag = false;
                        break;
                    }
                }
                if (flag) count++;
            }
        }

        return count;
    }


    private List<Integer> record = new ArrayList<>();
    private int nextN;

    /**
     * 每次尝试将 n = 质数 * (n2 * 质数)
     */
    public int smallestValue(int n) {

        boolean flag = true;
        while (flag) {
            nextN = 0;
            flag = dfs(n);
            if (nextN == n) {
                return n;
            }
            if (flag) n = nextN;
        }

        return n;
    }

    private boolean dfs(int n) {
        countPrimes(n);
        boolean flag = false;
        for (int zhi : record) {
            if (n == zhi) {
                nextN += zhi;
                return true;
            }

            if (n % zhi == 0) {
                nextN += zhi;
                flag = dfs(n / zhi);
                break;
            }
        }
        return flag;
    }

    public int countPrimes(int n) {
        int[] isPrime = new int[n];
        //1不是质数
        if (n == 0 || n == 1) {
            return 0;
        }
        int count = 0;
        //默认全是质数
        Arrays.fill(isPrime, 1);
        for (int i = 2; i < n; i++) {
            //如果i为合数，那么i的因子是之前一定存在一个数y，遍历到y的时候，一定将i设置为0了
            if (isPrime[i] == 1) {
                record.add(i);
                count++;
                //直接从 x*x 开始标记，因为 2x,3x,… 这些数一定在 x*x 之前就被其他数的倍数标记过了
                //2*3，2*4，... 3*3,3*4，...
                for (int j = i; (long) i * j < n; j++) {
                    isPrime[i * j] = 0;
                }
            }
        }
        return count;
    }

    /**
     * 6267. 添加边使所有节点度数都为偶数
     * 分类讨论：
     * 1，图中存在 0 个奇数点，直接返回 true
     * 2，图中存在 2 个奇数点
     * a，这两点没相连时，在之间加一条线连接，返回 true
     * b，这两点相连时，用两条线连在 这两点都没相连过的点上面，返回 true
     * 3，图中存在 4 个奇数点
     * 此时存在三种情况
     * a-b  c-d
     * a-c  b-d
     * a-d  b-c
     * 每种情况，必须之前没有相连过
     *
     * @return
     */
    public boolean isPossible(int n, List<List<Integer>> edges) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (List<Integer> edge : edges) {
            Set<Integer> set0 = map.get(edge.get(0));
            if (set0 == null) {
                set0 = new HashSet<>();
                map.put(edge.get(0), set0);
            }
            Set<Integer> set1 = map.get(edge.get(1));
            if (set1 == null) {
                set1 = new HashSet<>();
                map.put(edge.get(1), set1);
            }

            set0.add(edge.get(1));
            set1.add(edge.get(0));
        }

        List<Integer> list = new ArrayList<>();

        for (Map.Entry<Integer, Set<Integer>> entry : map.entrySet()) {
            if (entry.getValue().size() % 2 != 0) {
                list.add(entry.getKey());
            }
            if (list.size() > 4) return false;
        }

        if (list.size() == 2) {
            Set<Integer> set = new HashSet<>();
            set.add(list.get(0));
            set.addAll(map.get(list.get(0)));
            set.add(list.get(1));
            set.addAll(map.get(list.get(1)));

            return set.size() < n || isNotConnected(list.get(0), list.get(1), map);
        }

        if (list.size() == 4) {
            if (isNotConnected(list.get(0), list.get(1), map) &&
                    isNotConnected(list.get(2), list.get(3), map)) {
                return true;
            }
            if (isNotConnected(list.get(0), list.get(2), map) &&
                    isNotConnected(list.get(1), list.get(3), map)) {
                return true;
            }
            if (isNotConnected(list.get(0), list.get(3), map) &&
                    isNotConnected(list.get(1), list.get(2), map)) {
                return true;
            }
        }
        return list.size() == 0;
    }

    private boolean isNotConnected(int n1, int n2, Map<Integer, Set<Integer>> map) {
        return !map.get(n1).contains(n2);
    }

}
